package org.example.algorithm.dp;

/**
 * 完全平方数
 */

public class NumSquaresSolution {

    public static void main(String[] args) {
        NumSquaresSolution numSquaresSolution = new NumSquaresSolution();
        int res = numSquaresSolution.numSquares(82);
        System.out.println(res);
    }

    /**
     * 1, 4, 9, 16, 25
     * @param n
     * @return
     */
    public int numSquares(int n) {
        if (n == 1) {
            return 1;
        }
        int[] minLenArr = new int[n+1];
        minLenArr[0] = 0;
        minLenArr[1] = 1;
        for (int i=1;i<minLenArr.length;i++) {
            minLenArr[i] = n+1;
            for (int j=1;j*j<=i;j++) {
                if (i >= j*j) {
                    minLenArr[i] = Math.min(minLenArr[i], minLenArr[i-j*j] + 1);
                }
            }
        }
        return minLenArr[n];
    }

}
